/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 123
 * Date: 2023-07-20
 * Time: 9:32
 */
public class BinaryTree {

    static class Node{
      private int val ;
      private Node left ;
      private Node right ;

    public Node(int val){
        this.val = val ;
    }
    }

    public Node createTree(){
        Node A = new Node(1) ;
        Node B = new Node(2) ;
        Node C = new Node(3) ;
        Node D = new Node(4) ;
        Node E = new Node(5) ;
        Node F = new Node(6) ;
        A.left = B ;
        A.right = C ;
        B.left = D ;
        C.left = E ;
        C.right = F ;
   return A ;
    }

    public int nodeSize(Node root){
        if(root == null) return 0 ;
        return nodeSize(root.left) + nodeSize(root.right) + 1 ;

    }

    public int getLeafNodeCount(Node root){
     if(root == null) return 0 ;
     if(root.left == null && root.right == null)return 1 ;
      return getLeafNodeCount(root.left) + getLeafNodeCount(root.right) ;
    }

    public int getKLevelNodeCount(Node root , int k){
        if(root == null)return 0 ;
        return  getKLevelNodeCount2(root ,k , 1) ;
    }
    private int getKLevelNodeCount2(Node root , int k , int n){
        if(root == null )return 0 ;
        if(k == n) return 1 ;
        return getKLevelNodeCount2(root.left ,k , n + 1) + getKLevelNodeCount2(root.right,k,n+1) ;
    }

    public int getHeight(Node root){
        if(root == null) return 0 ;
        int leftHeight = getHeight(root.left) ;
        int rightHeight = getHeight(root.right) ;
      return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1 ;
    }

    public Node find(Node root , int val){
        if(root == null) return null ;
        if(root.val == val) return root ;
        Node left = find(root.left , val) ;
        if(left != null ) {
            return left ;
        }
        Node right = find(root.right , val) ;
        if(right != null ) {
            return right ;
        }
        return null ;
    }


}
